package binaryTree;

import java.util.ArrayList;
import java.util.List;

public class Class563 {

//    private final List<Integer> list = new ArrayList<>();
//    public int findTilt(TreeNode root) {
//        findTilt0(root);
//        int sum = 0;
//        for (Integer v : list) {
//            sum += v;
//        }
//        return sum;
//    }
//
//    private int findTilt0(TreeNode node) {
//        if (node == null) return 0;
//        if (node.left == null && node.right == null) return node.val;
//        int leftSum = findTilt0(node.left);
//        int rightSum = findTilt0(node.right);
//
//        list.add(Math.abs(leftSum-rightSum));
//        return leftSum + rightSum + node.val;
//    }


    List<Integer> list = new ArrayList<Integer>();

    public int findTilt(TreeNode root) {
        traverse(root);
int sum=0;
        for (Integer  a:list
             ) {
            sum+=a;

        }

return  sum;
    }


    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        int left = findTilt0(root.left);
        int right = findTilt0(root.right);
        list.add(Math.abs(left - right));
        traverse(root.left);
        traverse(root.right);
    }

//  CKG TODO 2023/4/5: 对遍历的理解还是有点狭隘  潜意识还是认为只有上面那样的写着遍历才是遍历  其实下面的也是遍历
    private int findTilt0(TreeNode node) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return node.val;
        int leftSum = findTilt0(node.left);
        int rightSum = findTilt0(node.right);
        return leftSum + rightSum + node.val;
    }




    public static void main(String[] args) {
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode7= new TreeNode(7);

       treeNode4.left=treeNode2;
       treeNode4.right=treeNode9;
       treeNode2.left=treeNode3;
       treeNode2.right=treeNode5;
       treeNode9.right=treeNode7;
        Class563 class563 = new Class563();
        int tilt = class563.findTilt(treeNode4);
        System.out.println(tilt);
    }

}
